package com.yhk.map;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

/**
 * @version 1.0
 * @Author moresuo
 * @Date 2024/10/28 13:20
 * @注释 拉链法实现HashMap
 */
public class MyChainingHashMap<K, V> {

    //元素节点
    static class Node<K,V>{
        K key;
        V value;
        Node(K key,V value){
            this.key=key;
            this.value=value;
        }
    }

    //使用链表数组作为底层数组
    private LinkedList<Node<K, V>>[] table ;
    //元素个数
    private int size;
    public MyChainingHashMap(int capacity){
        //容量必须大于0，也不能等于0，等于0进行取模运算时会报错
        capacity = Math.max(capacity, 1);
        table = new LinkedList[capacity];
        for(int i=0;i<table.length;i++){
            table[i] = new LinkedList<>();
        }
        //元素个数初始化
        size=0;
    }
    //默认初始化容量
    private static final int INIT_CAP=4;
    public MyChainingHashMap(){
        this(INIT_CAP);
    }

    /**
     * hash函数
     */
    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff)%table.length;
    }

    /**
     * 自动扩缩容
     */
    private void resize(int capacity) {
        //容量不能小于和等于0
        capacity = Math.max(capacity, 1);
        //创建一个新的Map
        MyChainingHashMap<K, V> newMap = new MyChainingHashMap<>(capacity);
        //将原先的元素进行转移
        for (LinkedList<Node<K,V>> list : table) {
            for (Node<K,V> node:list){
                newMap.put(node.key, node.value);
            }
        }
        this.table= newMap.table;
    }

    /**
     * 添加元素
     */
    public void put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }
        //获取索引
        LinkedList<Node<K, V>> list = table[hash(key)];
        //遍历列表，如果存在就替换，不存在就添加
        for (Node<K,V> node:list) {
            if (Objects.equals(node.key, key)) {
                node.value=value;
                return;
            }
        }
        //链表末尾添加元素
        list.add(new Node<>(key, value));
        //元素个数加一
        size++;
        //如果元素个数超过了负载因子，进行扩容
        if (size >= table.length * 0.75) {
            resize(table.length * 2);
        }
    }

    /**
     * 删除元素
     */
    public void remove(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }
        //获取索引
        LinkedList<Node<K, V>> list = table[hash(key)];
        //遍历链表
        for (Node<K, V> node : list) {
            if (Objects.equals(node.key, key)) {
                //执行删除
                list.remove(node);
                //个数减一
                size--;
                if (size <= table.length * 0.125) {
                    resize(table.length / 4);
                }
                return;
            }
        }
    }

    /**
     * 根据key查询
     */
    public V get(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }
        //获取索引
        LinkedList<Node<K, V>> list = table[hash(key)];
        //遍历链表
        for (Node<K, V> node : list) {
            if (Objects.equals(node.key, key)) {
                return node.value;
            }
        }
        return null;
    }
    /**
     * 返回所有key
     */
    public List<K> keys(){
        List<K> keys = new ArrayList<>();
        //遍历数组和链表
        for (LinkedList<Node<K, V>> list : table) {
            for (Node<K, V> node : list) {
                keys.add(node.key);
            }
        }
        return keys;
    }
    public int size(){
        return this.size;
    }
}
